package com.lz.find;

/**
 * BinarySearch..
 *
 * @author Lizhong
 * @date 2019/9/3
 */
public class BinarySearch {
    private static int count01;
    private static int count02;
    private static int count;



    public static int search(int[] t, int begin, int end, int key) {
        int middle;
        while (begin <= end) {
            middle = begin + (end - begin) / 2;
            count01++;
            if (key < t[middle]) end = middle - 1;
            else if (key > t[middle]) begin = middle + 1;

            else return middle;
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] a = {1, 5, 6, 7, 8, 9, 10, 20, 30, 65};
        // int search = search(a, 0, a.length - 1, 17);
        // System.out.println(search);
        method01(10000, 2356);
    }

    public static void method01(int n, int j) {
        int[] a = new int[n];
        for (int i = 0; i < a.length; i++) a[i] = i;
        int search = search(a, 0, a.length - 1, j);
        System.out.println(count01 + "," + search);
        int i = search02(a, 0, a.length - 1, j);
        System.out.println(count02 + "," + i); // 1次登录

    }

    /**
     * 差值,均匀分布比二分搜索快，反之亦然
     * mid=(low+high)/2, 即mid=low+1/2*(high-low);
     * 　　通过类比，我们可以将查找的点改进为如下：
     *
     * mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，此处有个坑，若low+(key-a[low])/(a[high]-a[low])<1,后面无论乘以多大个数都是0
     *
     * 查找成功或者失败的时间复杂度均为O(log2(log2n))。
     *
     * 查找成功或者失败的时间复杂度均为O(log2(log2n))。
     */
    public static int search02(int[] t, int begin, int end, int key) {
        int middle;
        while (begin <= end) {
            middle = begin + (key - t[begin]) * (end - begin) / (t[end] - t[begin]);
            count02++;
            if (key < t[middle]) end = middle - 1;
            else if (key > t[middle]) begin = middle + 1;
            else return middle;
        }
        return -1;
    }

}
